package com.Jancode.leetcode;

import java.util.*;

public class MinimumFuelCost {
    class Solution {
        // reconstruct the edge data structure of this problem
        private Map<Integer, List<Integer>> edges;
        private long fuel;   // the fuel is down-level variable(down to top)
        private int seats;

        public long minimumFuelCost(int[][] roads, int seats) {
            // initializing 
            this.edges = new HashMap<>();
            for(int[] road : roads) {
                edges.computeIfAbsent(road[0], k -> new ArrayList<>()).add(road[1]);
                edges.computeIfAbsent(road[1], k -> new ArrayList<>()).add(road[0]);
            }
            this.seats = seats;

            // the processing of the core problem
            dfs(0, -1);
            
            return this.fuel;
        }

        /**
         * 
         * @param current the current node to calculate the minimum fuel cost of the subtree of this node. 
         * @param parent  the parent node of the current node.             -- the top to down variable => induction demonstration convenience. 
         * @return the reprensentatives of this subtree of the current node.
         */
        private long dfs(int current, int parent) { // now, fuel is the costs of the subtree to current node.
            // The node itself has one representative.
            int representatives = 1;

            // This condition is to except the -1 and other empty graph etc. special cases.
            if(!edges.containsKey(current))
                return representatives;

            /*
             * Implementation Notes:
             * 
             *            w  => parent node
             *            |
             *            v  => current node   if the representatives are r sented from the subtree, then 
             *           / \                   atleast there are car ceil(r - 1/seats) from the subtree, and  
             *          s   t  => subtree      this node v has its owner car, so there are least ceil(r / seats)
             *         / \ / \
             *         ... ...                 em... fuel variable is the minimum fuel cost from the subtree children 
             *                                 to this current node.
             * Greedy method can demonstrate this method is ok.
             */

            // Consider the sub-forest of the current node.
            for(int child : edges.get(current)) {
                if(child != parent) {
                    // Add count of representatives in each child subtree
                    // to the parent subtree.
                    representatives += dfs(child, current);
                }
            }  // calculate the representatives in the current node  

            if(current != 0) {
                // Count the fuel it takes to move to the parent node.
                // Root node does not have any parent so we ignore it.
                this.fuel += Math.ceil((double) representatives / seats);       // now , fuel is the minimum cost to parent from current - specail case 
                // You can think this fuel variable as the least value required cars to trains the representatives.

                // this propery is an analysis mathematical property.
            }

            return representatives;
        }
    }
}